{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Copyright 2014 Brett Slatkin, Pearson Education Inc.\n",
    "#\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "\n",
    "# Preamble to mimick book environment\n",
    "import logging\n",
    "from pprint import pprint\n",
    "from sys import stdout as STDOUT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 1\n",
    "def insertion_sort(data):\n",
    "    result = []\n",
    "    for value in data:\n",
    "        insert_value(result, value)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 2\n",
    "def insert_value(array, value):\n",
    "    for i, existing in enumerate(array):\n",
    "        if existing > value:\n",
    "            array.insert(i, value)\n",
    "            return\n",
    "    array.append(value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 3\n",
    "from random import randint\n",
    "\n",
    "max_size = 10**4\n",
    "data = [randint(0, max_size) for _ in range(max_size)]\n",
    "test = lambda: insertion_sort(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3,\n",
       " 4,\n",
       " 5,\n",
       " 6,\n",
       " 7,\n",
       " 8,\n",
       " 9,\n",
       " 10,\n",
       " 12,\n",
       " 12,\n",
       " 12,\n",
       " 13,\n",
       " 13,\n",
       " 14,\n",
       " 14,\n",
       " 16,\n",
       " 16,\n",
       " 16,\n",
       " 17,\n",
       " 20,\n",
       " 20,\n",
       " 20,\n",
       " 22,\n",
       " 22,\n",
       " 29,\n",
       " 30,\n",
       " 31,\n",
       " 33,\n",
       " 33,\n",
       " 33,\n",
       " 35,\n",
       " 36,\n",
       " 37,\n",
       " 37,\n",
       " 39,\n",
       " 39,\n",
       " 40,\n",
       " 40,\n",
       " 41,\n",
       " 41,\n",
       " 42,\n",
       " 45,\n",
       " 46,\n",
       " 46,\n",
       " 46,\n",
       " 47,\n",
       " 48,\n",
       " 48,\n",
       " 52,\n",
       " 53,\n",
       " 54,\n",
       " 55,\n",
       " 55,\n",
       " 57,\n",
       " 58,\n",
       " 59,\n",
       " 60,\n",
       " 61,\n",
       " 62,\n",
       " 63,\n",
       " 63,\n",
       " 63,\n",
       " 64,\n",
       " 65,\n",
       " 65,\n",
       " 66,\n",
       " 67,\n",
       " 67,\n",
       " 68,\n",
       " 70,\n",
       " 70,\n",
       " 70,\n",
       " 70,\n",
       " 71,\n",
       " 72,\n",
       " 72,\n",
       " 75,\n",
       " 75,\n",
       " 78,\n",
       " 78,\n",
       " 79,\n",
       " 79,\n",
       " 81,\n",
       " 83,\n",
       " 83,\n",
       " 85,\n",
       " 85,\n",
       " 85,\n",
       " 85,\n",
       " 86,\n",
       " 87,\n",
       " 87,\n",
       " 89,\n",
       " 89,\n",
       " 90,\n",
       " 90,\n",
       " 96,\n",
       " 97,\n",
       " 97,\n",
       " 99,\n",
       " 100,\n",
       " 100,\n",
       " 102,\n",
       " 105,\n",
       " 105,\n",
       " 105,\n",
       " 105,\n",
       " 106,\n",
       " 106,\n",
       " 106,\n",
       " 106,\n",
       " 110,\n",
       " 110,\n",
       " 113,\n",
       " 113,\n",
       " 114,\n",
       " 115,\n",
       " 116,\n",
       " 117,\n",
       " 117,\n",
       " 118,\n",
       " 118,\n",
       " 119,\n",
       " 120,\n",
       " 121,\n",
       " 122,\n",
       " 123,\n",
       " 124,\n",
       " 125,\n",
       " 125,\n",
       " 126,\n",
       " 127,\n",
       " 128,\n",
       " 129,\n",
       " 129,\n",
       " 132,\n",
       " 132,\n",
       " 133,\n",
       " 133,\n",
       " 133,\n",
       " 134,\n",
       " 136,\n",
       " 138,\n",
       " 141,\n",
       " 141,\n",
       " 143,\n",
       " 143,\n",
       " 145,\n",
       " 147,\n",
       " 147,\n",
       " 148,\n",
       " 149,\n",
       " 150,\n",
       " 150,\n",
       " 153,\n",
       " 154,\n",
       " 155,\n",
       " 155,\n",
       " 156,\n",
       " 157,\n",
       " 158,\n",
       " 159,\n",
       " 161,\n",
       " 161,\n",
       " 161,\n",
       " 164,\n",
       " 164,\n",
       " 167,\n",
       " 167,\n",
       " 168,\n",
       " 168,\n",
       " 169,\n",
       " 169,\n",
       " 169,\n",
       " 171,\n",
       " 171,\n",
       " 173,\n",
       " 173,\n",
       " 174,\n",
       " 175,\n",
       " 176,\n",
       " 176,\n",
       " 178,\n",
       " 179,\n",
       " 180,\n",
       " 180,\n",
       " 180,\n",
       " 181,\n",
       " 183,\n",
       " 185,\n",
       " 186,\n",
       " 186,\n",
       " 188,\n",
       " 189,\n",
       " 189,\n",
       " 192,\n",
       " 192,\n",
       " 193,\n",
       " 193,\n",
       " 193,\n",
       " 193,\n",
       " 196,\n",
       " 198,\n",
       " 198,\n",
       " 198,\n",
       " 200,\n",
       " 200,\n",
       " 200,\n",
       " 205,\n",
       " 205,\n",
       " 205,\n",
       " 206,\n",
       " 206,\n",
       " 209,\n",
       " 209,\n",
       " 209,\n",
       " 211,\n",
       " 213,\n",
       " 216,\n",
       " 218,\n",
       " 219,\n",
       " 220,\n",
       " 220,\n",
       " 221,\n",
       " 221,\n",
       " 221,\n",
       " 223,\n",
       " 225,\n",
       " 227,\n",
       " 228,\n",
       " 229,\n",
       " 231,\n",
       " 231,\n",
       " 234,\n",
       " 235,\n",
       " 235,\n",
       " 236,\n",
       " 236,\n",
       " 237,\n",
       " 239,\n",
       " 243,\n",
       " 245,\n",
       " 246,\n",
       " 246,\n",
       " 246,\n",
       " 247,\n",
       " 250,\n",
       " 250,\n",
       " 251,\n",
       " 251,\n",
       " 253,\n",
       " 254,\n",
       " 258,\n",
       " 258,\n",
       " 260,\n",
       " 261,\n",
       " 261,\n",
       " 262,\n",
       " 262,\n",
       " 263,\n",
       " 264,\n",
       " 264,\n",
       " 264,\n",
       " 264,\n",
       " 265,\n",
       " 266,\n",
       " 267,\n",
       " 271,\n",
       " 272,\n",
       " 272,\n",
       " 273,\n",
       " 274,\n",
       " 275,\n",
       " 276,\n",
       " 277,\n",
       " 277,\n",
       " 278,\n",
       " 280,\n",
       " 285,\n",
       " 288,\n",
       " 289,\n",
       " 290,\n",
       " 290,\n",
       " 291,\n",
       " 292,\n",
       " 292,\n",
       " 292,\n",
       " 294,\n",
       " 295,\n",
       " 296,\n",
       " 296,\n",
       " 298,\n",
       " 298,\n",
       " 299,\n",
       " 301,\n",
       " 302,\n",
       " 303,\n",
       " 303,\n",
       " 304,\n",
       " 304,\n",
       " 304,\n",
       " 304,\n",
       " 304,\n",
       " 305,\n",
       " 305,\n",
       " 306,\n",
       " 306,\n",
       " 307,\n",
       " 309,\n",
       " 310,\n",
       " 311,\n",
       " 312,\n",
       " 313,\n",
       " 315,\n",
       " 316,\n",
       " 318,\n",
       " 319,\n",
       " 319,\n",
       " 321,\n",
       " 322,\n",
       " 322,\n",
       " 323,\n",
       " 324,\n",
       " 325,\n",
       " 325,\n",
       " 330,\n",
       " 331,\n",
       " 331,\n",
       " 331,\n",
       " 334,\n",
       " 335,\n",
       " 335,\n",
       " 336,\n",
       " 336,\n",
       " 338,\n",
       " 338,\n",
       " 339,\n",
       " 340,\n",
       " 341,\n",
       " 341,\n",
       " 343,\n",
       " 343,\n",
       " 344,\n",
       " 345,\n",
       " 346,\n",
       " 348,\n",
       " 348,\n",
       " 348,\n",
       " 348,\n",
       " 350,\n",
       " 353,\n",
       " 353,\n",
       " 353,\n",
       " 355,\n",
       " 355,\n",
       " 355,\n",
       " 355,\n",
       " 355,\n",
       " 356,\n",
       " 358,\n",
       " 358,\n",
       " 359,\n",
       " 359,\n",
       " 359,\n",
       " 360,\n",
       " 361,\n",
       " 361,\n",
       " 362,\n",
       " 363,\n",
       " 364,\n",
       " 365,\n",
       " 366,\n",
       " 367,\n",
       " 368,\n",
       " 374,\n",
       " 375,\n",
       " 377,\n",
       " 377,\n",
       " 378,\n",
       " 379,\n",
       " 382,\n",
       " 383,\n",
       " 384,\n",
       " 386,\n",
       " 386,\n",
       " 386,\n",
       " 387,\n",
       " 388,\n",
       " 389,\n",
       " 390,\n",
       " 390,\n",
       " 391,\n",
       " 392,\n",
       " 393,\n",
       " 393,\n",
       " 394,\n",
       " 395,\n",
       " 396,\n",
       " 396,\n",
       " 397,\n",
       " 398,\n",
       " 399,\n",
       " 399,\n",
       " 400,\n",
       " 400,\n",
       " 401,\n",
       " 402,\n",
       " 402,\n",
       " 403,\n",
       " 403,\n",
       " 404,\n",
       " 405,\n",
       " 406,\n",
       " 406,\n",
       " 409,\n",
       " 410,\n",
       " 411,\n",
       " 411,\n",
       " 412,\n",
       " 413,\n",
       " 413,\n",
       " 414,\n",
       " 416,\n",
       " 416,\n",
       " 418,\n",
       " 420,\n",
       " 420,\n",
       " 420,\n",
       " 423,\n",
       " 424,\n",
       " 424,\n",
       " 425,\n",
       " 427,\n",
       " 427,\n",
       " 429,\n",
       " 429,\n",
       " 429,\n",
       " 431,\n",
       " 431,\n",
       " 431,\n",
       " 432,\n",
       " 432,\n",
       " 432,\n",
       " 435,\n",
       " 437,\n",
       " 437,\n",
       " 438,\n",
       " 438,\n",
       " 439,\n",
       " 440,\n",
       " 441,\n",
       " 441,\n",
       " 441,\n",
       " 442,\n",
       " 443,\n",
       " 445,\n",
       " 446,\n",
       " 446,\n",
       " 450,\n",
       " 451,\n",
       " 451,\n",
       " 451,\n",
       " 452,\n",
       " 453,\n",
       " 453,\n",
       " 454,\n",
       " 455,\n",
       " 456,\n",
       " 458,\n",
       " 458,\n",
       " 459,\n",
       " 459,\n",
       " 460,\n",
       " 460,\n",
       " 461,\n",
       " 461,\n",
       " 461,\n",
       " 463,\n",
       " 463,\n",
       " 464,\n",
       " 464,\n",
       " 464,\n",
       " 464,\n",
       " 465,\n",
       " 465,\n",
       " 468,\n",
       " 468,\n",
       " 468,\n",
       " 469,\n",
       " 470,\n",
       " 473,\n",
       " 476,\n",
       " 477,\n",
       " 477,\n",
       " 479,\n",
       " 480,\n",
       " 480,\n",
       " 481,\n",
       " 482,\n",
       " 484,\n",
       " 484,\n",
       " 484,\n",
       " 485,\n",
       " 486,\n",
       " 488,\n",
       " 489,\n",
       " 489,\n",
       " 490,\n",
       " 490,\n",
       " 490,\n",
       " 491,\n",
       " 491,\n",
       " 492,\n",
       " 493,\n",
       " 494,\n",
       " 495,\n",
       " 496,\n",
       " 499,\n",
       " 502,\n",
       " 505,\n",
       " 505,\n",
       " 506,\n",
       " 506,\n",
       " 507,\n",
       " 507,\n",
       " 508,\n",
       " 510,\n",
       " 512,\n",
       " 512,\n",
       " 512,\n",
       " 514,\n",
       " 515,\n",
       " 515,\n",
       " 517,\n",
       " 517,\n",
       " 518,\n",
       " 518,\n",
       " 518,\n",
       " 519,\n",
       " 519,\n",
       " 520,\n",
       " 520,\n",
       " 520,\n",
       " 521,\n",
       " 523,\n",
       " 525,\n",
       " 526,\n",
       " 526,\n",
       " 526,\n",
       " 529,\n",
       " 529,\n",
       " 531,\n",
       " 532,\n",
       " 533,\n",
       " 535,\n",
       " 536,\n",
       " 541,\n",
       " 541,\n",
       " 542,\n",
       " 543,\n",
       " 544,\n",
       " 546,\n",
       " 549,\n",
       " 551,\n",
       " 551,\n",
       " 552,\n",
       " 554,\n",
       " 555,\n",
       " 556,\n",
       " 558,\n",
       " 558,\n",
       " 562,\n",
       " 562,\n",
       " 562,\n",
       " 563,\n",
       " 564,\n",
       " 565,\n",
       " 565,\n",
       " 566,\n",
       " 569,\n",
       " 569,\n",
       " 571,\n",
       " 576,\n",
       " 577,\n",
       " 579,\n",
       " 580,\n",
       " 581,\n",
       " 581,\n",
       " 582,\n",
       " 582,\n",
       " 583,\n",
       " 584,\n",
       " 585,\n",
       " 585,\n",
       " 588,\n",
       " 589,\n",
       " 589,\n",
       " 589,\n",
       " 591,\n",
       " 592,\n",
       " 592,\n",
       " 593,\n",
       " 594,\n",
       " 595,\n",
       " 596,\n",
       " 597,\n",
       " 598,\n",
       " 599,\n",
       " 599,\n",
       " 600,\n",
       " 601,\n",
       " 604,\n",
       " 604,\n",
       " 604,\n",
       " 605,\n",
       " 605,\n",
       " 606,\n",
       " 606,\n",
       " 610,\n",
       " 612,\n",
       " 613,\n",
       " 613,\n",
       " 616,\n",
       " 617,\n",
       " 618,\n",
       " 618,\n",
       " 619,\n",
       " 621,\n",
       " 622,\n",
       " 622,\n",
       " 623,\n",
       " 626,\n",
       " 626,\n",
       " 627,\n",
       " 628,\n",
       " 629,\n",
       " 632,\n",
       " 635,\n",
       " 636,\n",
       " 636,\n",
       " 637,\n",
       " 638,\n",
       " 641,\n",
       " 641,\n",
       " 643,\n",
       " 644,\n",
       " 644,\n",
       " 644,\n",
       " 645,\n",
       " 646,\n",
       " 646,\n",
       " 648,\n",
       " 648,\n",
       " 650,\n",
       " 650,\n",
       " 650,\n",
       " 650,\n",
       " 651,\n",
       " 652,\n",
       " 652,\n",
       " 653,\n",
       " 653,\n",
       " 654,\n",
       " 654,\n",
       " 655,\n",
       " 656,\n",
       " 657,\n",
       " 658,\n",
       " 660,\n",
       " 661,\n",
       " 665,\n",
       " 666,\n",
       " 669,\n",
       " 669,\n",
       " 670,\n",
       " 671,\n",
       " 673,\n",
       " 674,\n",
       " 675,\n",
       " 675,\n",
       " 676,\n",
       " 676,\n",
       " 678,\n",
       " 678,\n",
       " 681,\n",
       " 682,\n",
       " 683,\n",
       " 684,\n",
       " 685,\n",
       " 690,\n",
       " 692,\n",
       " 693,\n",
       " 694,\n",
       " 694,\n",
       " 695,\n",
       " 696,\n",
       " 702,\n",
       " 702,\n",
       " 702,\n",
       " 702,\n",
       " 703,\n",
       " 703,\n",
       " 704,\n",
       " 704,\n",
       " 705,\n",
       " 705,\n",
       " 706,\n",
       " 708,\n",
       " 709,\n",
       " 709,\n",
       " 710,\n",
       " 710,\n",
       " 711,\n",
       " 711,\n",
       " 714,\n",
       " 716,\n",
       " 716,\n",
       " 717,\n",
       " 717,\n",
       " 720,\n",
       " 720,\n",
       " 721,\n",
       " 722,\n",
       " 722,\n",
       " 723,\n",
       " 725,\n",
       " 725,\n",
       " 726,\n",
       " 727,\n",
       " 730,\n",
       " 731,\n",
       " 731,\n",
       " 731,\n",
       " 732,\n",
       " 732,\n",
       " 734,\n",
       " 734,\n",
       " 735,\n",
       " 735,\n",
       " 735,\n",
       " 736,\n",
       " 737,\n",
       " 737,\n",
       " 742,\n",
       " 743,\n",
       " 743,\n",
       " 749,\n",
       " 751,\n",
       " 751,\n",
       " 752,\n",
       " 753,\n",
       " 753,\n",
       " 756,\n",
       " 756,\n",
       " 756,\n",
       " 757,\n",
       " 758,\n",
       " 759,\n",
       " 762,\n",
       " 764,\n",
       " 764,\n",
       " 765,\n",
       " 765,\n",
       " 767,\n",
       " 771,\n",
       " 773,\n",
       " 776,\n",
       " 777,\n",
       " 782,\n",
       " 784,\n",
       " 785,\n",
       " 785,\n",
       " 785,\n",
       " 787,\n",
       " 788,\n",
       " 790,\n",
       " 791,\n",
       " 791,\n",
       " 792,\n",
       " 792,\n",
       " 793,\n",
       " 800,\n",
       " 803,\n",
       " 803,\n",
       " 803,\n",
       " 804,\n",
       " 804,\n",
       " 804,\n",
       " 804,\n",
       " 808,\n",
       " 808,\n",
       " 809,\n",
       " 810,\n",
       " 819,\n",
       " 819,\n",
       " 820,\n",
       " 820,\n",
       " 822,\n",
       " 822,\n",
       " 824,\n",
       " 824,\n",
       " 824,\n",
       " 825,\n",
       " 826,\n",
       " 828,\n",
       " 828,\n",
       " 831,\n",
       " 832,\n",
       " 834,\n",
       " 834,\n",
       " 835,\n",
       " 836,\n",
       " 836,\n",
       " 836,\n",
       " 840,\n",
       " 840,\n",
       " 841,\n",
       " 841,\n",
       " 841,\n",
       " 842,\n",
       " 842,\n",
       " 842,\n",
       " 843,\n",
       " 843,\n",
       " 844,\n",
       " 846,\n",
       " 846,\n",
       " 846,\n",
       " 847,\n",
       " 851,\n",
       " 851,\n",
       " 851,\n",
       " 852,\n",
       " 852,\n",
       " 852,\n",
       " 855,\n",
       " 855,\n",
       " 856,\n",
       " 856,\n",
       " 861,\n",
       " 861,\n",
       " 862,\n",
       " 864,\n",
       " 864,\n",
       " 867,\n",
       " 868,\n",
       " 869,\n",
       " 870,\n",
       " 870,\n",
       " 871,\n",
       " 872,\n",
       " 873,\n",
       " 874,\n",
       " 874,\n",
       " 875,\n",
       " 875,\n",
       " 876,\n",
       " 877,\n",
       " 877,\n",
       " 878,\n",
       " 879,\n",
       " 879,\n",
       " 879,\n",
       " 879,\n",
       " 880,\n",
       " 881,\n",
       " 881,\n",
       " 882,\n",
       " 882,\n",
       " 885,\n",
       " 886,\n",
       " 887,\n",
       " 888,\n",
       " 888,\n",
       " 889,\n",
       " 890,\n",
       " 891,\n",
       " 893,\n",
       " 894,\n",
       " 895,\n",
       " 897,\n",
       " 899,\n",
       " 901,\n",
       " 902,\n",
       " 902,\n",
       " 904,\n",
       " 906,\n",
       " 908,\n",
       " 909,\n",
       " 909,\n",
       " 910,\n",
       " 910,\n",
       " 912,\n",
       " 913,\n",
       " 913,\n",
       " 913,\n",
       " 914,\n",
       " 917,\n",
       " 918,\n",
       " 918,\n",
       " 921,\n",
       " 923,\n",
       " 923,\n",
       " 923,\n",
       " 924,\n",
       " 924,\n",
       " 925,\n",
       " 926,\n",
       " 926,\n",
       " 928,\n",
       " 929,\n",
       " 931,\n",
       " 933,\n",
       " 934,\n",
       " 935,\n",
       " 936,\n",
       " 936,\n",
       " 936,\n",
       " 938,\n",
       " 939,\n",
       " 939,\n",
       " 940,\n",
       " 940,\n",
       " 940,\n",
       " 941,\n",
       " 941,\n",
       " 942,\n",
       " 942,\n",
       " 942,\n",
       " 943,\n",
       " 943,\n",
       " 947,\n",
       " 947,\n",
       " 947,\n",
       " 948,\n",
       " 948,\n",
       " 948,\n",
       " 950,\n",
       " 951,\n",
       " 951,\n",
       " 952,\n",
       " 952,\n",
       " 952,\n",
       " 954,\n",
       " 954,\n",
       " 955,\n",
       " 955,\n",
       " 957,\n",
       " 957,\n",
       " 959,\n",
       " 959,\n",
       " 960,\n",
       " 960,\n",
       " 961,\n",
       " 963,\n",
       " 963,\n",
       " 964,\n",
       " 964,\n",
       " 966,\n",
       " 967,\n",
       " 969,\n",
       " 970,\n",
       " 970,\n",
       " 972,\n",
       " 972,\n",
       " 973,\n",
       " 974,\n",
       " 975,\n",
       " 976,\n",
       " 976,\n",
       " 981,\n",
       " 982,\n",
       " 984,\n",
       " 987,\n",
       " 988,\n",
       " 988,\n",
       " 990,\n",
       " 990,\n",
       " 991,\n",
       " 991,\n",
       " 991,\n",
       " 991,\n",
       " 992,\n",
       " 992,\n",
       " 994,\n",
       " 995,\n",
       " 996,\n",
       " 996,\n",
       " 996,\n",
       " 997,\n",
       " 998,\n",
       " 999,\n",
       " 1000,\n",
       " 1000,\n",
       " 1003,\n",
       " 1003,\n",
       " 1004,\n",
       " 1004,\n",
       " 1004,\n",
       " 1007,\n",
       " ...]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example 4\n",
    "from cProfile import Profile\n",
    "\n",
    "profiler = Profile()\n",
    "profiler.runcall(test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         20003 function calls in 2.111 seconds\n",
      "\n",
      "   Ordered by: cumulative time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "        1    0.000    0.000    2.111    2.111 <ipython-input-4-7cd656f86a1e>:6(<lambda>)\n",
      "        1    0.007    0.007    2.111    2.111 <ipython-input-2-6d2e4e80022e>:2(insertion_sort)\n",
      "    10000    2.085    0.000    2.104    0.000 <ipython-input-3-ea74c835a3cd>:2(insert_value)\n",
      "     9994    0.018    0.000    0.018    0.000 {method 'insert' of 'list' objects}\n",
      "        6    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<pstats.Stats at 0x103e615f8>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example 5\n",
    "import sys\n",
    "from pstats import Stats\n",
    "\n",
    "stats = Stats(profiler)\n",
    "stats = Stats(profiler, stream=STDOUT)\n",
    "stats.strip_dirs()\n",
    "stats.sort_stats('cumulative')\n",
    "stats.print_stats()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         30003 function calls in 0.052 seconds\n",
      "\n",
      "   Ordered by: cumulative time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "        1    0.000    0.000    0.052    0.052 <ipython-input-4-7cd656f86a1e>:6(<lambda>)\n",
      "        1    0.013    0.013    0.052    0.052 <ipython-input-2-6d2e4e80022e>:2(insertion_sort)\n",
      "    10000    0.011    0.000    0.038    0.000 <ipython-input-7-99320b136ae1>:4(insert_value)\n",
      "    10000    0.018    0.000    0.018    0.000 {method 'insert' of 'list' objects}\n",
      "    10000    0.010    0.000    0.010    0.000 {built-in method _bisect.bisect_left}\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<pstats.Stats at 0x103e78390>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example 6\n",
    "from bisect import bisect_left\n",
    "\n",
    "def insert_value(array, value):\n",
    "    i = bisect_left(array, value)\n",
    "    array.insert(i, value)\n",
    "\n",
    "profiler = Profile()\n",
    "profiler.runcall(test)\n",
    "stats = Stats(profiler, stream=STDOUT)\n",
    "stats.strip_dirs()\n",
    "stats.sort_stats('cumulative')\n",
    "stats.print_stats()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example 7\n",
    "def my_utility(a, b):\n",
    "    c = 1\n",
    "    for i in range(100):\n",
    "        c += a * b\n",
    "\n",
    "def first_func():\n",
    "    for _ in range(1000):\n",
    "        my_utility(4, 5)\n",
    "\n",
    "def second_func():\n",
    "    for _ in range(10):\n",
    "        my_utility(1, 3)\n",
    "\n",
    "def my_program():\n",
    "    for _ in range(20):\n",
    "        first_func()\n",
    "        second_func()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         20242 function calls in 0.255 seconds\n",
      "\n",
      "   Ordered by: cumulative time\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "        1    0.000    0.000    0.255    0.255 <ipython-input-8-0997c49da643>:15(my_program)\n",
      "       20    0.008    0.000    0.253    0.013 <ipython-input-8-0997c49da643>:7(first_func)\n",
      "    20200    0.247    0.000    0.247    0.000 <ipython-input-8-0997c49da643>:2(my_utility)\n",
      "       20    0.000    0.000    0.002    0.000 <ipython-input-8-0997c49da643>:11(second_func)\n",
      "        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
      "\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<pstats.Stats at 0x103ee56a0>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example 8\n",
    "profiler = Profile()\n",
    "profiler.runcall(my_program)\n",
    "stats = Stats(profiler, stream=STDOUT)\n",
    "stats.strip_dirs()\n",
    "stats.sort_stats('cumulative')\n",
    "stats.print_stats()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   Ordered by: cumulative time\n",
      "\n",
      "Function                                          was called by...\n",
      "                                                      ncalls  tottime  cumtime\n",
      "<ipython-input-8-0997c49da643>:15(my_program)     <- \n",
      "<ipython-input-8-0997c49da643>:7(first_func)      <-      20    0.008    0.253  <ipython-input-8-0997c49da643>:15(my_program)\n",
      "<ipython-input-8-0997c49da643>:2(my_utility)      <-   20000    0.245    0.245  <ipython-input-8-0997c49da643>:7(first_func)\n",
      "                                                         200    0.002    0.002  <ipython-input-8-0997c49da643>:11(second_func)\n",
      "<ipython-input-8-0997c49da643>:11(second_func)    <-      20    0.000    0.002  <ipython-input-8-0997c49da643>:15(my_program)\n",
      "{method 'disable' of '_lsprof.Profiler' objects}  <- \n",
      "\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<pstats.Stats at 0x103ee5438>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example 9\n",
    "stats = Stats(profiler, stream=STDOUT)\n",
    "stats.strip_dirs()\n",
    "stats.sort_stats('cumulative')\n",
    "stats.print_callers()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
